package usually;
//96. 不同的二叉搜索树
public class Num96_numTrees {
    public int numTrees(int n) {
        int []G = new int[n + 1];
        G[0] = 1;
        G[1] = 1;
        for (int i = 2; i <= n; i++) {
            //i表示数组下标，及以i为节点个数的二叉树序列的数量
            for (int j = 1; j <= i ; j++) {
                //j表示以不同的节点作为根节点
                G[i] += G[j - 1] * G[i - j];
            }

        }
        return G[n];

    }
}
